package main

import (
	"fmt"
	"math/rand"
	"time"
)

//TODO : 时间复杂度 T(N) = O(N^3)
func MaxSum1(number []int) (max int) {
	t := time.Now()
	max = 0
	for i := 0; i < len(number)-1; i++ {
		for j := i; j < len(number)-1; j++ {
			sum := 0
			for k := i; k <= j; k++ {
				sum += number[k]
			}
			if sum > max {
				max = sum
			}
		}
	}
	fmt.Println("Values:", max, "TODO1:", time.Since(t), )
	return max
}

//TODO : 时间复杂度 T(N) = O(N^2)
func MaxSum2(number []int) (max int) {
	t := time.Now()
	max = 0
	for i := 0; i < len(number)-1; i++ {
		sum := 0
		for j := i; j <= len(number)-1; j++ {
			sum += number[j]
			if sum > max {
				max = sum
			}
		}
	}
	fmt.Println("Values:", max, "TODO2:", time.Since(t), )
	return max
}

//TODO : 时间复杂度 T(N) = O(N)
func MaxSum3(number []int) (max int) {
	t := time.Now()
	sum := 0
	max = 0
	for i := 0; i < len(number)-1; i++ {
		sum += number[i]
		if sum > max {
			max = sum
		}
		if sum < 0 {
			sum = 0
		}
	}
	fmt.Println("Values:", max, "TODO3:", time.Since(t), )
	return max
}

func main() {

	//TODO : 生成数据
	rand.Seed(time.Now().Unix())
	number := make([]int, 3000, 1000000)
	for k, _ := range number {
		number[k] = rand.Intn(50) - 25
	}

	//TODO : 1
	MaxSum1(number)

	//TODO : 2
	MaxSum2(number)

	//TODO : 3
	MaxSum3(number)
}
